package code.oldCode.dynamic;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class LongestIncreasingSubsequence {

    /**
     * 300. 最长递增子序列
     *
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        // 可以用二分压缩到nlogn，没看
        int len = nums.length;
        int[] dp = new int[len];
        int ans = 1;
        for (int i = 0; i < len; i++) {
            if (i == 0) dp[i] = 1;
            else {
                dp[i] = 1;
                for (int j = 0; j < i; j++) {
                    if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                ans = Math.max(dp[i], ans);
            }
        }
        return ans;
    }

    /**
     * 673. 最长递增子序列的个数
     *
     * @param nums
     * @return
     */
    public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        int[] dp_ans = new int[len];
        int ans = 0, ans_num = 0;
        for (int i = 0; i < len; i++) {
            dp[i] = 1;
            dp_ans[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (dp[i] < dp[j] + 1) {
                        dp[i] = dp[j] + 1;
                        dp_ans[i] = dp_ans[j];
                    } else if (dp[i] == dp[j] + 1) {
                        dp_ans[i] += dp_ans[j];
                    }
                }
            }
            if (dp[i] > ans) {
                ans = dp[i];
                ans_num = dp_ans[i];
            } else if (dp[i] == ans) {
                ans_num += dp_ans[i];
            }
        }

        return ans_num;
    }

    /**
     * 646. 最长数对链
     *
     * @param pairs
     * @return
     */
    public int findLongestChain(int[][] pairs) {
        int len = pairs.length;
        Comparator<int[]> comparator = (o1, o2) -> {
            if (o1[0] != o2[0])
                return o1[0] - o2[0];
            else
                return o1[1] - o2[1];
        };
        Arrays.sort(pairs, comparator);
        int[] dp = new int[len];
        int ans = 0;
        for (int i = 0; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (pairs[i][0] > pairs[j][1]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    /**
     * 1218. 最长定差子序列
     *
     * @param arr
     * @param difference
     * @return
     */
    public int longestSubsequence(int[] arr, int difference) {
        // 如此使用O(n^2)的dp会超时
        int len = arr.length;
        int[] dp = new int[len];
        int ans = 0;
        for (int i = 0; i < len; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] - arr[j] == difference) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    /**
     * 1218. 最长定差子序列——不超时
     * @param arr
     * @param difference
     * @return
     */
    public int longestSubsequence_(int[] arr, int difference) {
        // 使用map做dp
        Map<Integer, Integer> dp = new HashMap<>();
        int ans = 0;
        for (int num : arr) {
            dp.put(num, dp.getOrDefault(num - difference, 0) + 1);
            ans = Math.max(ans, dp.get(num));
        }
        return ans;
    }

    /**
     * 1027. 最长等差数列
     *
     * @param nums
     * @return
     */
    public int longestArithSeqLength(int[] nums) {
        // ※ 需要注意到条件：0 <= nums[i] <= 500 ※
        int min = Arrays.stream(nums).min().getAsInt();
        int max = Arrays.stream(nums).max().getAsInt();
        int difference = max - min;
        int ans = 1;
        for (int diff = -difference; diff <= difference; diff++) {
            int[] dp = new int[max + 1];
            // 先赋值-1表示没有
            Arrays.fill(dp, -1);
            for (int num : nums) {
                if (min <= num - diff && num - diff <= max && dp[num - diff] != -1) {
                    dp[num] = Math.max(dp[num], dp[num - diff] + 1);
                    ans = Math.max(ans, dp[num]);
                }
                dp[num] = Math.max(dp[num], 1);
            }
        }
        return ans;
    }

    /**
     * 1027. 最长等差数列——比较慢，但比上面的官方题解好想
     * @param nums
     * @return
     */
    public int longestArithSeqLength_(int[] nums) {
        int len = nums.length;
        HashMap<Integer, Integer>[] maps = new HashMap[len];
        for (int i = 0; i < len; i++) {
            maps[i] = new HashMap<>();
        }
        int ans = 1;
        // 只有第一个数的情况，长度都是1
        for (int i = -500; i <= 500 ; i++) {
            maps[0].put(i, 1);
        }
        // 后面的数，长度最小为2
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                if (maps[j].containsKey(diff)) {
                    maps[i].put(diff, maps[j].get(diff) + 1);
                } else {
                    maps[i].put(diff, 2);
                }
                ans = Math.max(ans, maps[i].get(diff));
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        LongestIncreasingSubsequence longestIncreasingSubsequence = new LongestIncreasingSubsequence();
        System.out.println(longestIncreasingSubsequence.longestArithSeqLength_(new int[]{24, 13, 1, 100, 0, 94, 3, 0, 3}));
    }
}
